package alfabeta;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


public class SudokuSolver implements ISudokuSolver {

	int[][] puzzle;
	int size;
	ArrayList<ArrayList<Integer>> D; // ArrayList of Arrays for storing domains of each variable
	int[][] testPuzzle = {
			{0,5,7,0,0,0,0,0,9},
			{0,8,0,0,3,0,6,0,0},
			{3,0,9,7,0,8,4,0,2},
			{0,0,0,8,1,0,2,4,0},
			{0,0,8,0,9,0,5,0,0},
			{0,4,6,0,5,3,0,0,0},
			{8,0,5,3,0,6,9,0,1},
			{0,0,2,0,7,0,0,8,0},
			{4,0,0,0,0,0,7,6,0}
	};

	@Override
	public int[][] getPuzzle() {
		return puzzle;
	}

	@Override
	public void setValue(int col, int row, int value) {
		puzzle[col][row] = value;
	}


	@Override
	public void setup(int sizeIn) {
		size = sizeIn;
		int numOfVars = size*size*size*size; // total number of variables
		puzzle = new int[size*size][size*size]; // i.e 9x9 fields
		// readInPuzzle(testPuzzle);

		D = new ArrayList<ArrayList<Integer>>(numOfVars); // i.e 81 Domain-lists

		// Add initial domain to each variable
		for (int i = 0; i < numOfVars ; i++ ) {

			ArrayList<Integer> initialDomain = new ArrayList<Integer>(size*size);
			for (int j=1; j <= size*size; j++) { // i.e initial domain is 1-9 for 9x9 board
				initialDomain.add(j);	
			}

			D.add(i, initialDomain);
		}
	}


	@Override
	public boolean solve() {

		ArrayList<Integer> asn = GetAssignment(puzzle);

		// First we check the validity of the initial assignment
		// If any column/row/diagonal contains 2 (non-zero) equal values, the assignment is invalid

		for (int i=0 ; i < asn.size(); i++){
			// if variable assigned a value
			if (asn.get(i)!=0) {
				// get relevant variables and check
				Set<Integer> relevantVars = new HashSet<Integer>();
				relevantVars.addAll(GetRelevantVariables(i));

				for (Integer var: relevantVars) {
					if(asn.get(var).equals(asn.get(i))) return false; // assignment invalid
				}
			}
		}

		// Apply Initial forward Checking and restrict domains, and remove unnecessary varibles form domains
		INITIAL_FC(asn);

		// Start forward checking to find a solution
		ArrayList<Integer> solution = FC(asn);

		// If a solution is found then add it to board
		if (solution != null) {
			for (int i = 0 ; i<solution.size() ; i++) {
				this.setValue(GetRow(i), GetColumn(i), solution.get(i));
			}
			return true; // solution found
		}

		return false; // no solution was found
	}

	@Override
	public void readInPuzzle(int[][] p) {
		puzzle = p;
	}

	// Forward checking picks first unassigned variable (= 0) and do forward checking with backtracking
	public ArrayList<Integer> FC(ArrayList<Integer> asn) {

		//System.out.println(asn.toString());

		int firstUnassigned = -1;

		// Pick first unassigned 
		for (int index = 0; index < asn.size() ; index++) {
			if (asn.get(index) == 0) {
				firstUnassigned = index; // set index of first unassigned
				System.out.println("first unassigned found at: " + index);
				break;
			}
		}

		// If assignment is complete - no unassigned (0) was found
		if (firstUnassigned == -1) {
			System.out.println("assignment complete");
			return asn; // return the complete assignment		
		}


		// Start forward Checking - copy Domains to new temp
		ArrayList<ArrayList<Integer>> oldD = this.copyOfDomains(D);

		System.out.println("domain at "+ firstUnassigned + " : "  + D.get(firstUnassigned));

		ArrayList<Integer> Q = new ArrayList<Integer>();
		for (Integer v: D.get(firstUnassigned)) Q.add(v);

		// for all values in the domain of firstUnassigned
		for (Integer v: Q) 
		{
			// check arc consistency and assign variable if consistent
			if (AC_FC(firstUnassigned, v)) { // arc consistent

				asn.set(firstUnassigned, v); // variable found - set value

				// Forward check from next
				if (FC(asn) != null) {

					return FC(asn); 
				}

				else {
					asn.set(firstUnassigned, 0);
					D = this.copyOfDomains(oldD);

				}	
			} 

			else // If Arc consistency not preserved, remove reset domains and remove variable

			{
				// reset Domains
				D = this.copyOfDomains(oldD); 

				// remove from useless variable from domain
				D.get(firstUnassigned).remove(v);
			}
		}

		return null; //failure
	}


	//------------------------------------------------------------------
	//				AC_FC
	//
	// Implementation of arc-consistency for forward-checking AC-FC(cv).
	// This is a key component of FC algorithm, and the only function you need to 
	// use in your FC(asn) implementation
	//------------------------------------------------------------------
	public boolean AC_FC(Integer X, Integer V){
		//Reduce domain Dx
		D.get(X).clear();
		D.get(X).add(V);

		//Put in Q all relevant Y where Y>X
		ArrayList<Integer> Q = new ArrayList<Integer>(); //list of all relevant Y
		int col = GetColumn(X);
		int row = GetRow(X);
		int cell_x = row / size;
		int cell_y = col / size;

		//all variables in the same column
		for (int i=0; i<size*size; i++){
			if (GetVariable(i,col) > X) {
				Q.add(GetVariable(i,col));
			}
		}
		//all variables in the same row
		for (int j=0; j<size*size; j++){
			if (GetVariable(row,j) > X) {
				Q.add(GetVariable(row,j));
			}
		}
		//all variables in the same size*size box
		for (int i=cell_x*size; i<=cell_x*size + 2; i++) {
			for (int j=cell_y*size; j<=cell_y*size + 2; j++){
				if (GetVariable(i,j) > X) {
					Q.add(GetVariable(i,j));
				}
			}
		}

		//REVISE(Y,X)
		boolean consistent = true;
		while (!Q.isEmpty() && consistent){
			Integer Y = Q.remove(0);
			if (REVISE(Y,X)) {
				consistent = !D.get(Y).isEmpty();
			}
		}
		return consistent;
	}	


	//------------------------------------------------------------------
	//				REVISE 
	//------------------------------------------------------------------
	public boolean REVISE(int Xi, int Xj){
		Integer zero = new Integer(0);

		assert(Xi >= 0 && Xj >=0);
		assert(Xi < size*size*size*size && Xj <size*size*size*size);
		assert(Xi != Xj);

		boolean DELETED = false;

		ArrayList<Integer> Di = D.get(Xi);
		ArrayList<Integer> Dj = D.get(Xj);	

		for (int i=0; i<Di.size(); i++){
			Integer vi = Di.get(i);
			ArrayList<Integer> xiEqVal = new ArrayList<Integer>(size*size*size*size);	
			for (int var=0; var<size*size*size*size; var++){
				xiEqVal.add(var,zero);				
			}

			xiEqVal.set(Xi,vi);

			boolean hasSupport = false;	
			for (int j=0; j<Dj.size(); j++){
				Integer vj = Dj.get(j);
				if (CONSISTENT(xiEqVal, Xj, vj)) {
					hasSupport = true;
					break;
				}
			}

			if (hasSupport == false) {
				Di.remove(vi);
				DELETED = true;
			}

		}

		return DELETED;
	}




	//------------------------------------------------------------------
	//CONSISTENT: 
	//
	//Given a partial assignment "asn"  checks whether its extension with 
	//variable = val is consistent with Sudoku rules, i.e. whether it violates
	//any of constraints whose all variables in the scope have been assigned. 
	//This implicitly encodes all constraints describing Sudoku.
	//
	//Before it returns, it undoes the temporary assignment variable=val
	//It can be used as a building block for REVISE and AC-FC
	//
	//NOTE: the procedure assumes that all assigned values are in the range 
	// 		{0,..,9}. 
	//-------------------------------------------------------------------
	public boolean CONSISTENT(ArrayList<Integer> asn, Integer variable, Integer val) {
		Integer v1,v2;

		//variable to be assigned must be clear
		assert(asn.get(variable) == 0);
		asn.set(variable,val);

		//alldiff(col[i])
		for (int i=0; i<size*size; i++) {
			for (int j=0; j<size*size; j++) {
				for (int k=0; k<size*size; k++) {
					if (k != j) {
						v1 = asn.get(GetVariable(i,j));
						v2 = asn.get(GetVariable(i,k));
						if (v1 != 0 && v2 != 0 && v1.compareTo(v2) == 0) {
							asn.set(variable,0);
							return false;
						}
					}
				}
			}
		}



		//alldiff(row[j])
		for (int j=0; j<size*size; j++) {
			for (int i=0; i<size*size; i++) {
				for (int k=0; k<size*size; k++) {
					if (k != i) {
						v1 = asn.get(GetVariable(i,j));
						v2 = asn.get(GetVariable(k,j));
						if (v1 != 0 && v2 != 0 && v1.compareTo(v2) == 0) {
							asn.set(variable,0);			 				
							return false;
						}
					}
				}
			}
		}


		//alldiff(block[size*i,size*j])
		for (int i=0; i<size; i++) {
			for (int j=0; j<size; j++) {
				for (int i1 = 0; i1<size; i1++) {
					for (int j1=0; j1<size; j1++) {
						int var1 = GetVariable(size*i + i1, size*j + j1);
						for (int i2 = 0; i2<size; i2++) {
							for (int j2=0; j2<size; j2++) {
								int var2 = GetVariable(size*i+i2, size*j + j2);
								if (var1 != var2) {
									v1 = asn.get(var1);
									v2 = asn.get(var2);
									if (v1 != 0 && v2 != 0 && v1.compareTo(v2) == 0) {
										asn.set(variable,0);	 		 			 				
										return false;
									}
								}
							}
						}

					}
				}
			}
		}

		asn.set(variable,0);
		return true;
	}	


	//------------------------------------------------------------------
	//						INITIAL_FC
	//------------------------------------------------------------------
	public boolean INITIAL_FC(ArrayList<Integer> anAssignment) {
		//Enforces consistency between unassigned variables and all 
		//initially assigned values; 
		for (int i=0; i<anAssignment.size(); i++){
			Integer V = anAssignment.get(i);
			if (V != 0){
				ArrayList<Integer> Q = GetRelevantVariables(i);
				boolean consistent = true;
				while (!Q.isEmpty() && consistent){
					Integer Y = Q.remove(0);
					if (REVISE(Y,i)) {
						consistent = !D.get(Y).isEmpty();
					}
				}	
				if (!consistent) return false;
			}
		}

		return true;
	}


	//------------------------------------------------------------------
	//						GetRelevantVariables
	//------------------------------------------------------------------
	public ArrayList<Integer> GetRelevantVariables(Integer X){
		//Returns all variables that are interdependent of X, i.e. 
		//all variables involved in a binary constraint with X
		ArrayList<Integer> Q = new ArrayList<Integer>(); //list of all relevant Y
		int col = GetColumn(X);
		int row = GetRow(X);
		int cell_x = row / size;
		int cell_y = col / size;

		//all variables in the same column
		for (int i=0; i<size*size; i++){
			if (GetVariable(i,col) != X) {
				Q.add(GetVariable(i,col));
			}
		}
		//all variables in the same row
		for (int j=0; j<size*size; j++){
			if (GetVariable(row,j) != X) {
				Q.add(GetVariable(row,j));
			}
		}
		//all variables in the same size*size cell
		for (int i=cell_x*size; i<=cell_x*size + 2; i++) {
			for (int j=cell_y*size; j<=cell_y*size + 2; j++){
				if (GetVariable(i,j) != X) {
					Q.add(GetVariable(i,j));
				}
			}
		}	

		return Q;
	}





	//------------------------------------------------------------------
	// Functions translating between the puzzle and an assignment
	//-------------------------------------------------------------------
	public ArrayList<Integer> GetAssignment(int[][] p) {
		ArrayList<Integer> asn = new ArrayList<Integer>();
		for (int i=0; i<size*size; i++) {
			for (int j=0; j<size*size; j++) {
				asn.add(GetVariable(i,j), new Integer(p[i][j]));
				if (p[i][j] != 0){
					//restrict domain
					D.get(GetVariable(i,j)).clear();
					D.get(GetVariable(i,j)).add(new Integer(p[i][j]));
				}
			}
		}
		return asn;
	}	


	@SuppressWarnings("rawtypes")
	public int[][] GetPuzzle(ArrayList asn) {
		int[][] p = new int[size*size][size*size];
		for (int i=0; i<size*size; i++) {
			for (int j=0; j<size*size; j++) {
				Integer val = (Integer) asn.get(GetVariable(i,j));
				p[i][j] = val.intValue();
			}
		}
		return p;
	}


	//------------------------------------------------------------------
	//Utility functions
	//-------------------------------------------------------------------
	public int GetVariable(int i, int j){
		assert(i<size*size && j<size*size);
		assert(i>=0 && j>=0);		
		return (i*size*size + j);	
	}	


	public int GetRow(int X){
		return (X / (size*size)); 	
	}	

	public int GetColumn(int X){
		return X - ((X / (size*size))*size*size);	
	}	

	private void printDomains(){
		int num = 0;
		for (ArrayList<Integer> d : D) {
			System.out.println(num++ + " : " + d.toString());
		}
	}

	private void printDomains(ArrayList<ArrayList<Integer>> domains){


		for (ArrayList<Integer> d : domains) {
			System.out.println(d.toString());
		}
	}

	private ArrayList<ArrayList<Integer>> copyOfDomains (ArrayList<ArrayList<Integer>> domains) {

		ArrayList<ArrayList<Integer>> copy = new ArrayList<ArrayList<Integer>>(domains.size());

		for (ArrayList<Integer> dom: domains) {
			ArrayList<Integer> domCopy = new ArrayList<Integer>(dom.size());
			for (Integer var: dom) {
				domCopy.add(var);
			}
			copy.add(domCopy);
		}

		return copy;

	}

}
